package leetcode.D100.T17;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {

    // 一刷
    /*private static final List<Character>[] mappping = new List[10];
    static {
        char c = 'a';
        for(int i=2; i<mappping.length; ++i) {
            mappping[i] = new ArrayList<>();
            int k = (i==7 || i==9) ? 4 : 3;
            for(int j=0; j<k; ++j) {
                mappping[i].add(c);
                c = (char) (c + 1);
            }
        }
    }

    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if(digits.length() == 0) {
            return result;
        }
        dfs(result, new StringBuilder(), digits, 0);
        return result;
    }
    private void dfs(List<String> result, StringBuilder sb, String digits, int cur) {
        if(cur == digits.length()) {
            result.add(sb.toString());
            return;
        }
        List<Character> charset = mappping[digits.charAt(cur)-'0'];
        for (Character c : charset) {
            sb.append(c);
            dfs(result, sb, digits, cur+1);
            sb.deleteCharAt(sb.length()-1);
        }
    }*/

    // 二刷
    private final static Map<Integer, String> mapping = new HashMap<>();
    static {
        int idx = 0;
        for (int i=2; i<=9; ++i) {
            int len = (i == 7 || i == 9) ? 4 : 3;
            StringBuilder sb = new StringBuilder();
            for (int j=0; j<len; ++j) {
                char c = (char) (idx + 'a');
                sb.append(c);
                idx++;
            }
            mapping.put(i, sb.toString());
        }
    }

    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits.length() == 0)
            return result;
        StringBuilder path = new StringBuilder();
        dfs(result, path, digits, 0);
        return result;
    }

    private void dfs(List<String> result, StringBuilder path, String digits, int cur) {
        if (digits.length() == cur) {
            result.add(path.toString());
            return;
        }
        String s = mapping.get(digits.charAt(cur) - '0');
        for (int i=0; i<s.length(); ++i) {
            path.append(s.charAt(i));
            dfs(result, path, digits, cur+1);
            path.deleteCharAt(path.length()-1);
        }
    }
}
